package main

func main() {
	println("这是一个快排示例")
}

func QuickSort(arr []int) {
	quickSort(arr, 0, len(arr)-1)
}

func quickSort(arr []int, left int, right int) {
	if left >= right {
		return
	}
	pivotIndex := partition(arr, left, right)
	quickSort(arr, left, pivotIndex-1)
	println("0000000000000000")
	quickSort(arr, pivotIndex+1, right)
}

// 划分函数
func partition(arr []int, left int, right int) int {
	// 以 arr[left] 为枢轴
	pivot := arr[left]
	for left < right {
		// 找到第一个比枢轴小的位置
		for left < right && arr[right] >= pivot {
			right--
		}
		arr[left] = arr[right]
		// 找到第一个比枢轴大的位置
		for left < right && arr[left] <= pivot {
			left++
		}
		arr[right] = arr[left]
	}
	// 将枢轴放置到正确位置上
	arr[left] = pivot
	println("划分函数success")
	return left
}
